﻿//#include <iostream>
//#include <fstream>
//#include <sstream>
//#include <map>
//#include <cstring>
//using namespace std;
//
//typedef char** HuffmanCode;
//typedef struct {
//    char data;
//    int weight;
//    int parent, lchild, rchild;
//} HTNode, * HuffmanTree;
//
//// 选择两个最小权重的节点
//void Select(HTNode*& HT, int len, int& s1, int& s2) {
//    int min1 = 9999, min2 = 9999;
//    for (int i = 1; i <= len; i++) {
//        if (HT[i].weight < min1 && HT[i].parent == 0) {
//            min2 = min1;
//            s2 = s1;
//            min1 = HT[i].weight;
//            s1 = i;
//        }
//        else if (HT[i].weight < min2 && HT[i].parent == 0) {
//            min2 = HT[i].weight;
//            s2 = i;
//        }
//    }
//}
////将手动输入的字符权值存入文件中
//void save1(HuffmanTree& HT, int n)
//{
//    ofstream outfile("hand_char.txt", ios::out);
//    if (!outfile)
//    {
//        cerr << "文件打开失败" << endl;
//        return;
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        outfile << HT[i].data << " " << HT[i].weight << endl;
//    }
//    outfile.close();
//}
//// 创建霍夫曼树（手动输入字符和权重）
//void Create_tree1(HuffmanTree& HT, int n) {
//    int m = 2 * n - 1;
//    HT = new HTNode[m + 1];
//    for (int i = 1; i <= m; i++) {
//        HT[i].parent = 0;
//        HT[i].lchild = 0;
//        HT[i].rchild = 0;
//        HT[i].data = '\0';
//    }
//    for (int i = 1; i <= n; i++) {
//        cout << "请输入字符: ";
//        cin >> HT[i].data;
//        cout << HT[i].data << " 的权重: ";
//        cin >> HT[i].weight;
//    }
//    for (int i = n + 1; i <= m; i++) {
//        int s1, s2;
//        Select(HT, i - 1, s1, s2);
//        HT[s1].parent = i;
//        HT[s2].parent = i;
//        HT[i].lchild = s1;
//        HT[i].rchild = s2;
//        HT[i].weight = HT[s1].weight + HT[s2].weight;
//    }
//    save1(HT,n);
//}
//
//// 生成霍夫曼编码
//void Creat_code(HuffmanTree& HT, HuffmanCode& HC, int n) {
//    int start, c, f;
//    HC = new char* [n + 1];
//    char* cd = new char[n];
//    cd[n - 1] = '\0';
//    for (int i = 1; i <= n; i++) {
//        start = n - 1;
//        c = i;
//        f = HT[i].parent;
//        while (f != 0) {
//            --start;
//            if (HT[f].lchild == c) cd[start] = '0';
//            else cd[start] = '1';
//            c = f; f = HT[f].parent;
//        }
//        HC[i] = new char[n - start + 1];
//        strcpy_s(HC[i], n - start + 1, &cd[start]);
//    }
//    delete[] cd;
//}
//
//// 输出霍夫曼编码
//void print(HuffmanTree HT, HuffmanCode& HC, int n) {
//    for (int i = 1; i <= n; i++) {
//        if (HT[i].data == ' ') {
//            cout << "空格" << " 的霍夫曼编码: " << HC[i] << endl;
//        }
//        else {
//            cout << HT[i].data << " 的霍夫曼编码: " << HC[i] << endl;
//        }
//    }
//}
//
//// 保存字符串到文件
//void save2(string data) {
//    ofstream outfile("char.txt", ios::out);
//    if (!outfile) {
//        cerr << "文件保存失败" << endl;
//        return;
//    }
//    outfile << data << endl;
//    outfile.close();
//}
//
//// 从文件读取字符串并统计字符频率
//void read2(map<char, int>& my_string) {
//    ifstream infile("char.txt", ios::in);
//    if (!infile) {
//        cerr << "文件读取失败" << endl;
//        return;
//    }
//    string line;
//    while (getline(infile, line)) {
//        for (char ch : line) {
//            my_string[ch] += 1;
//        }
//    }
//    infile.close();
//}
//
//// 根据统计的字符频率创建霍夫曼树
//void Create_tree2(HuffmanTree& HT, int n, map<char, int>& my_string) {
//    int m = 2 * n - 1;
//    HT = new HTNode[m + 1];
//    for (int i = 1; i <= m; i++) {
//        HT[i].parent = 0;
//        HT[i].lchild = 0;
//        HT[i].rchild = 0;
//        HT[i].data = '\0';
//    }
//    int i = 1;
//    for (auto& pair : my_string) {
//        HT[i].data = pair.first;
//        HT[i].weight = pair.second;
//        i++;
//    }
//    for (int i = n + 1; i <= m; i++) {
//        int s1, s2;
//        Select(HT, i - 1, s1, s2);
//        HT[s1].parent = i;
//        HT[s2].parent = i;
//        HT[i].lchild = s1;
//        HT[i].rchild = s2;
//        HT[i].weight = HT[s1].weight + HT[s2].weight;
//    }
//}
//
////读取文件1
//void read1(HuffmanTree& HT, int& n) {
//    ifstream infile("hand_char.txt", ios::in);
//    if (!infile) {
//        cerr << "文件打开失败" << endl;
//        return;
//    }
//    string line;
//    int i = 0;
//     
//    // 计算文件中的行数
//    while (getline(infile, line)) {
//        i++;
//    }
//    n = i;
//    infile.clear();//清除文件流状态
//    infile.seekg(0, ios::beg);
//
//    int m = 2 * n - 1;
//    HT = new HTNode[m + 1];
//    for (int i = 1; i <= m; i++) {
//        HT[i].parent = 0;
//        HT[i].lchild = 0;
//        HT[i].rchild = 0;
//        HT[i].data = '\0';
//        HT[i].weight = 0;
//    }
//
//    i = 1;
//    while (getline(infile, line)) {
//        istringstream iss(line);
//        if (!(iss >> HT[i].data >> HT[i].weight)) {
//            cout << "文件格式错误" << endl;
//            return;
//        }
//        cout << "读取到的字符: " << HT[i].data << ", 权重: " << HT[i].weight << endl; // 调试信息
//        i++;
//    }
//    infile.close();
//
//    // 构建霍夫曼树
//    for (int i = n + 1; i <= m; i++) {
//        int s1, s2;
//        Select(HT, i - 1, s1, s2);
//        HT[s1].parent = i;
//        HT[s2].parent = i;
//        HT[i].lchild = s1;
//        HT[i].rchild = s2;
//        HT[i].weight = HT[s1].weight + HT[s2].weight;
//    }
//}
//
////读取文件：构造哈夫曼编码
//void Creat_code1(HuffmanTree& HT, HuffmanCode& HC, int &n) {
//    int start, c, f;
//    HC = new char* [n + 1];
//    char* cd = new char[n];
//    cd[n - 1] = '\0';
//    for (int i = 1; i <= n; i++) {
//        start = n - 1;
//        c = i;
//        f = HT[i].parent;
//        while (f != 0) {
//            --start;
//            if (HT[f].lchild == c) cd[start] = '0';
//            else cd[start] = '1';
//            c = f; f = HT[f].parent;
//        }
//        HC[i] = new char[n - start + 1];
//        strcpy_s(HC[i], n - start + 1, &cd[start]);
//    }
//    delete[] cd;
//}
//// 读取文件：输出霍夫曼编码
//void print1(HuffmanTree& HT, HuffmanCode& HC, int count, string data) {
//    for (char ch : data) { // 遍历输入字符串的每个字符
//        bool found = false;
//        for (int j = 1; j <= count; j++) { // 遍历霍夫曼树的叶子节点
//            if (HT[j].data == ch) {
//                cout << HC[j]; // 输出对应的霍夫曼编码
//                found = true;
//                break;
//            }
//        }
//        if (!found) {
//            cout << "存在字符无哈夫曼编码: " << ch << endl;
//            return;
//        }
//    }
//    cout << endl; // 在所有字符编码输出完成后换行
//}
////译码
//void decode(HuffmanTree HT,HuffmanCode HC1, string data,int count)
//{
//    string temp;
//    for (size_t i= 0; i<data.size(); i++) 
//    {
//        temp += data[i];
//        for (int j=0;j<=count;j++) 
//        {
//            if (HC1[j]==temp) 
//            {
//                cout << HT[j].data;
//            }
//        }
//        temp.clear();
//    }
//
//}
//// 菜单
//void menu() {
//    cout << "1. 手动输入字符和权重生成霍夫曼树并存入文件中" << endl;
//    cout << "2. 从字符串生成霍夫曼树并输出霍夫曼编码" << endl;
//    cout << "3. 通过读取文件来构建霍夫曼树进行编码" << endl;
//    cout << "4.译码" << endl;
//    cout << "0.退出系统" << endl;
//}
//
//int main() {
//    HuffmanTree HT1;
//    HuffmanCode HC1;
//    HuffmanTree HT2;
//    HuffmanCode HC2;
//
//    while (1) {
//        menu();
//        int n;
//        string choice;
//        cin >> choice;
//        cin.ignore(); // 清除缓冲区
//        if (choice == "1") {
//            cout << "请输入字符数量: ";
//            cin >> n;
//            if (isdigit(n)) 
//            {
//                cout<<"请输入有效值" << endl;
//                break;
//            }
//            Create_tree1(HT1, n);
//            Creat_code(HT1, HC1, n);
//            print(HT1, HC1, n);
//        }
//        else if (choice == "2") {
//            map<char, int> my_string;
//            string data;
//            cout << "请输入字符串: ";
//            getline(cin, data);
//            save2(data);
//            read2(my_string);
//            n = my_string.size();
//            Create_tree2(HT2, n, my_string);
//            Creat_code(HT2, HC2, n);
//            print(HT2, HC2, n);
//        }
//        else if (choice=="3")
//        {
//            int count;
//            read1(HT1,count);
//            string data;
//            cout << "请输入字符串: ";
//            getline(cin, data);
//            Creat_code1(HT1, HC1, count);
//            print1(HT1,HC1,count,data);
//        }
//        else if (choice == "4") 
//        {
//            int count;
//            read1(HT1, count);
//            Creat_code1(HT1, HC1, count);
//            cout<<"请输入密码序列" << endl;
//            string data;
//            cin >> data;
//            decode( HT1, HC1, data,count);
//        }
//        else if(choice=="0")
//        {
//            exit(0);
//        }
//        system("pause");
//        system("cls");
//    }
//    return 0;
//}

#include <iostream>
#include <fstream>
#include <sstream>
#include <map>
#include <cstring>
using namespace std;

typedef char** HuffmanCode;
typedef struct {
    char data;
    int weight;
    int parent, lchild, rchild;
} HTNode, * HuffmanTree;

// 选择两个最小权重的节点
void Select(HTNode*& HT, int len, int& s1, int& s2) {
    int min1 = 9999, min2 = 9999;
    for (int i = 1; i <= len; i++) {
        if (HT[i].weight < min1 && HT[i].parent == 0) {
            min2 = min1;
            s2 = s1;
            min1 = HT[i].weight;
            s1 = i;
        }
        else if (HT[i].weight < min2 && HT[i].parent == 0) {
            min2 = HT[i].weight;
            s2 = i;
        }
    }
}
//将手动输入的字符权值存入文件中
void save1(HuffmanTree& HT, int n)
{
    ofstream outfile("hand_char.txt", ios::out);
    if (!outfile)
    {
        cerr << "文件打开失败" << endl;
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        outfile << HT[i].data << " " << HT[i].weight << endl;
    }
    outfile.close();
}
// 创建霍夫曼树（手动输入字符和权重）
void Create_tree1(HuffmanTree& HT, int n) {
    int m = 2 * n - 1;
    HT = new HTNode[m + 1];
    for (int i = 1; i <= m; i++) {
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
        HT[i].data = '\0';
    }
    for (int i = 1; i <= n; i++) {
        cout << "请输入字符: ";
        cin >> HT[i].data;
        cout << HT[i].data << " 的权重: ";
        cin >> HT[i].weight;
    }
    for (int i = n + 1; i <= m; i++) {
        int s1, s2;
        Select(HT, i - 1, s1, s2);
        HT[s1].parent = i;
        HT[s2].parent = i;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
    save1(HT,n);
}

// 生成霍夫曼编码
void Creat_code(HuffmanTree& HT, HuffmanCode& HC, int n) {
    int start, c, f;
    HC = new char* [n + 1];
    char* cd = new char[n];
    cd[n - 1] = '\0';
    for (int i = 1; i <= n; i++) {
        start = n - 1;
        c = i;
        f = HT[i].parent;
        while (f != 0) {
            --start;
            if (HT[f].lchild == c) cd[start] = '0';
            else cd[start] = '1';
            c = f; f = HT[f].parent;
        }
        HC[i] = new char[n - start + 1];
        strcpy_s(HC[i], n - start + 1, &cd[start]);
    }
    delete[] cd;
}

// 输出霍夫曼编码
void print(HuffmanTree HT, HuffmanCode& HC, int n) {
    for (int i = 1; i <= n; i++) {
        if (HT[i].data == ' ') {
            cout << "空格" << " 的霍夫曼编码: " << HC[i] << endl;
        }
        else {
            cout << HT[i].data << " 的霍夫曼编码: " << HC[i] << endl;
        }
    }
}

// 保存字符串到文件
void save2(string data) {
    ofstream outfile("char.txt", ios::out);
    if (!outfile) {
        cerr << "文件保存失败" << endl;
        return;
    }
    outfile << data << endl;
    outfile.close();
}

// 从文件读取字符串并统计字符频率
void read2(map<char, int>& my_string) {
    ifstream infile("char.txt", ios::in);
    if (!infile) {
        cerr << "文件读取失败" << endl;
        return;
    }
    string line;
    while (getline(infile, line)) {
        for (char ch : line) {
            my_string[ch] += 1;
        }
    }
    infile.close();
}

// 根据统计的字符频率创建霍夫曼树
void Create_tree2(HuffmanTree& HT, int n, map<char, int>& my_string) {
    int m = 2 * n - 1;
    HT = new HTNode[m + 1];
    for (int i = 1; i <= m; i++) {
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
        HT[i].data = '\0';
    }
    int i = 1;
    for (auto& pair : my_string) {
        HT[i].data = pair.first;
        HT[i].weight = pair.second;
        i++;
    }
    for (int i = n + 1; i <= m; i++) {
        int s1, s2;
        Select(HT, i - 1, s1, s2);
        HT[s1].parent = i;
        HT[s2].parent = i;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}

//读取文件1
void read1(HuffmanTree& HT, int& n) {
    ifstream infile("hand_char.txt", ios::in);
    if (!infile) {
        cerr << "文件打开失败" << endl;
        return;
    }
    string line;
    int i = 0;
     
    // 计算文件中的行数
    while (getline(infile, line)) {
        i++;
    }
    n = i;
    infile.clear();//清除文件流状态
    infile.seekg(0, ios::beg);

    int m = 2 * n - 1;
    HT = new HTNode[m + 1];
    for (int i = 1; i <= m; i++) {
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
        HT[i].data = '\0';
        HT[i].weight = 0;
    }

    i = 1;
    while (getline(infile, line)) {
        istringstream iss(line);
        if (!(iss >> HT[i].data >> HT[i].weight)) {
            cout << "文件格式错误" << endl;
            return;
        }
        cout << "读取到的字符: " << HT[i].data << ", 权重: " << HT[i].weight << endl; // 调试信息
        i++;
    }
    infile.close();

    // 构建霍夫曼树
    for (int i = n + 1; i <= m; i++) {
        int s1, s2;
        Select(HT, i - 1, s1, s2);
        HT[s1].parent = i;
        HT[s2].parent = i;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}

//读取文件：构造哈夫曼编码
void Creat_code1(HuffmanTree& HT, HuffmanCode& HC, int &n) {
    int start, c, f;
    HC = new char* [n + 1];
    char* cd = new char[n];
    cd[n - 1] = '\0';
    for (int i = 1; i <= n; i++) {
        start = n - 1;
        c = i;
        f = HT[i].parent;
        while (f != 0) {
            --start;
            if (HT[f].lchild == c) cd[start] = '0';
            else cd[start] = '1';
            c = f; f = HT[f].parent;
        }
        HC[i] = new char[n - start + 1];
        strcpy_s(HC[i], n - start + 1, &cd[start]);
    }
    delete[] cd;
}
// 读取文件：输出霍夫曼编码
void print1(HuffmanTree& HT, HuffmanCode& HC, int count, string data) {
    for (char ch : data) { // 遍历输入字符串的每个字符
        bool found = false;
        for (int j = 1; j <= count; j++) { // 遍历霍夫曼树的叶子节点
            if (HT[j].data == ch) {
                cout << HC[j]; // 输出对应的霍夫曼编码
                found = true;
                break;
            }
        }
        if (!found) {
            cout << "存在字符无哈夫曼编码: " << ch << endl;
            return;
        }
    }
    cout << endl; // 在所有字符编码输出完成后换行
}
//译码
//void decode(HuffmanTree HT,HuffmanCode HC1, string data,int count)
//{
//    string temp;
//    for (size_t i= 0; i<data.size(); i++) 
//    {
//        temp += data[i];
//        for (int j=0;j<=count;j++) 
//        {
//            if (HC1[j]==temp) 
//            {
//                cout << HT[j].data;
//            }
//        }
//        temp.clear();
//    }
//
//}
void decode(HuffmanTree HT, string data, int count) {
    int root = 2 * count - 1; // 霍夫曼树的根节点索引
    int current = root; // 当前节点初始化为根节点

    for (size_t i = 0; i < data.size(); i++) {
        if (data[i] == '0') {
            current = HT[current].lchild; // 向左子树移动
        }
        else if (data[i] == '1') {
            current = HT[current].rchild; // 向右子树移动
        }
        else {
            cout << "无效的编码字符: " << data[i] << endl;
            return;
        }

        // 检查是否到达叶子节点
        if (HT[current].lchild == 0 && HT[current].rchild == 0) {
            cout << HT[current].data; // 输出叶子节点对应的字符
            current = root; // 重新从根节点开始
        }
    }
    cout << endl; // 输出换行
}
// 菜单
void menu() {
    cout << "1. 手动输入字符和权重生成霍夫曼树并存入文件中" << endl;
    cout << "2. 从字符串生成霍夫曼树并输出霍夫曼编码" << endl;
    cout << "3. 通过读取文件来构建霍夫曼树进行编码" << endl;
    cout << "4.译码" << endl;
    cout << "0.退出系统" << endl;
}

int main() {
    HuffmanTree HT1;
    HuffmanCode HC1;
    HuffmanTree HT2;
    HuffmanCode HC2;

    while (1) {
        menu();
        int n;
        string choice;
        cin >> choice;
        cin.ignore(); // 清除缓冲区
        if (choice == "1") {
            cout << "请输入字符数量: ";
            cin >> n;
            if (isdigit(n)) 
            {
                cout<<"请输入有效值" << endl;
                break;
            }
            Create_tree1(HT1, n);
            Creat_code(HT1, HC1, n);
            print(HT1, HC1, n);
        }
        else if (choice == "2") {
            map<char, int> my_string;
            string data;
            cout << "请输入字符串: ";
            getline(cin, data);
            save2(data);
            read2(my_string);
            n = my_string.size();
            Create_tree2(HT2, n, my_string);
            Creat_code(HT2, HC2, n);
            print(HT2, HC2, n);
        }
        else if (choice=="3")
        {
            int count;
            read1(HT1,count);
            string data;
            cout << "请输入字符串: ";
            getline(cin, data);
            Creat_code1(HT1, HC1, count);
            print1(HT1,HC1,count,data);
        }
        else if (choice == "4") 
        {
            int count;
            read1(HT1, count);
            Creat_code1(HT1, HC1, count);
            cout<<"请输入密码序列" << endl;
            string data;
            cin >> data;
            decode( HT1, data,count);
        }
        else if(choice=="0")
        {
            exit(0);
        }
        system("pause");
        system("cls");
    }
    return 0;
}

